数据结构和算法-栈（[逆]波兰表达式）

什么是栈？
[1]栈的英文名为Stack
[2]栈是一个先入后出（FILO-Firest In Last Out）的有序列表
[3]栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
[4]根据栈的定义可知，最先放入栈的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

出栈和入栈

入栈（push）：
在这里插入图片描述
出栈（pop）：

栈的应用场景

[1]子程序的调用：在跳往子程序前，会先将一下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
[2]处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
[3]表达式的转换与求值（实际解决）。
[4]二叉树的遍历。
[5]图形的深度优先（depth-first）搜索算法。

栈的快速入门

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来存储栈的数据内容。
思路分析：
[1]使用数组模拟栈
[2]定义一个top表示栈顶，初始值为-1
[3]入栈的操作，当有数据加入到栈时，top++；stack[top]=data；
[4]出栈的操作，int value=stack[top];top–,return value;
代码实现：

//定义一个类表示栈结构
class ArrayStack{
	private int maxSize;//栈的大小
	private int[] stack;//数组，模拟栈，数据就放在该数组中
	private int top = -1;//栈顶，初始化为-1
	//构造器
	public ArrayStack(int maxSize){
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	//栈满
	public boolean isFull(){
		return top == maxSize-1;
	}
	//栈空
	public boolean isEmpty(){
		return top == -1;
	}
	//入栈
	public void push(int value){
		//先判断栈是否满
		if(isFull()){
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	//出栈,将栈顶的数组返回
	public int pop(){
		//先判断栈是否空
		if(isEmpty()){
			//抛出异常
			throw new RuntimeException("栈空，没有数据~");
		}
		int value = stack[top];
		top--;
		return value;
	}
	//显示栈的情况(遍历栈),遍历时，需要从栈顶开始显示数据
	public void list(){
		if(isEmpty()){
			System.out.println("栈空~");
			return;
		}
		for(int i = top;i >= 0;i--){
			System.out.printf("stack[%d]=%d\n",i,stack[i]);
		}
	}
}

栈实现综合计算器（中缀表达式）

中缀表达式：
[1]中缀表达式就是常见的运算表达式：如(3+4)X5-6
[2]中缀表达式的求值是我们人最熟悉的，但是对于计算机来说却不好操作，因此在计算结果时，往往会将中缀表达式转换成其它表达式来操作
是用栈完成表达式的计算思路：
[1]通过一个index值（索引），来遍历我们的表达式
[2]创建两个栈，一个存放数值的栈，一个存放符号的栈
[3]如果发现是一个数字，就直接放入数栈
[4]如果发现的是一个符号，就分如下情况
（1）如果发现当前的符号栈为空，就直接入栈
（2）如果符号栈有操作符，就进行比较，如果当前的操作符的有限级小于或者等于栈中的操作符，就需要从数栈栈pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈
（3）如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
[5]当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号并运行。
[6]最后在数栈中只有一个数字，就是表达式的结果。

代码：
栈结构：

class ArrayStack2{
	private int maxSize;//栈的大小
	private int[] stack;//数组，模拟栈，数据就放在该数组中
	private int top = -1;//栈顶，初始化为-1
	public ArrayStack2(int maxSize){//构造器
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	//查看栈顶的值，不是真正的出栈
	public int peek(){
		return stack[top];
	}
	public boolean isFull(){//栈满
		return top == maxSize-1;
	}
	public boolean isEmpty(){//栈空
		return top == -1;
	}
	public void push(int value){//入栈
		//先判断栈是否满
		if(isFull()){
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	public int pop(){//出栈,将栈顶的数组返回
		//先判断栈是否空
		if(isEmpty()){
			//抛出异常
			throw new RuntimeException("栈空，没有数据~");
		}
		int value = stack[top];
		top--;
		return value;
	}
	public void list(){	//显示栈的情况(遍历栈),遍历时，需要从栈顶开始显示数据
		if(isEmpty()){
			System.out.println("栈空~");
			return;
		}
		for(int i = top;i >= 0;i--){
			System.out.printf("stack[%d]=%d\n",i,stack[i]);
		}
	}
	//返回运算符的优先级，优先级使用数字表示，数字越大优先级越高
	public int priority(int oper){
		if(oper == '*' || oper == '/')return 1;
		else if(oper == '+' || oper == '-') return 0;
		else return -1;//表达式只有+-*/
	}
	//判断是不是一个运算符
	public boolean isOper(char val){
		return val == '+' || val == '-' || val == '*' || val == '/';
	}
	//计算方法
	public int cal(int num1,int num2,int oper){
		int res = 0;//res用于存放计算结果
		switch (oper) {
		case '+':
			res = num1 + num2;
			break;
		case '-':
			res = num2 - num1;//注意顺序
			break;
		case '*':
			res = num1 * num2;
			break;
		case '/':
			res = num2 / num1;
			break;
		default:
			break;
		}
		return res;
	}
}

测试代码：

public static void main(String[] args) {
	//表达式
	String expression = "3+2*6-2";
	//创建两个栈，一个是数栈，一个是符号栈
	ArrayStack2 numStack = new ArrayStack2(10);
	ArrayStack2 operStack = new ArrayStack2(10);
	//定义相关变量
	int index = 0;//用于扫描
	int num1 = 0;
	int num2 = 0;
	int oper = 0;
	int res = 0;
	String keepNum="";
	char ch = ' ';//将每次扫描得到的结果保存到ch中
	//开始while循环扫描
	while(true){
		//依次得到expression的每一个字符
		ch = expression.substring(index, index+1).charAt(0);
		//判断ch是什么，然后做相应的处理
		if(operStack.isOper(ch)){//如果是运算符
			//判断当前的符号栈是否为空
			if(!operStack.isEmpty()){
				//如果符号栈有操作符，就进行比较，如果当前的操作符的有限级小于或者等于栈中的操作符
				//就需要从数栈栈pop出两个数，在从符号栈中pop出一个符号，进行运算
				//将得到的结果，入数栈，然后将当前的操作符入符号栈
				if(operStack.priority(ch) <= operStack.priority(operStack.peek())){
					num1 = numStack.pop();
					num2 = numStack.pop();
					oper = operStack.pop();
					res = numStack.cal(num1, num2, oper);
					//把运算的结果入数栈
					numStack.push(res);
					//然后把当前的操作符入符号栈
					operStack.push(ch);
				}else{
					//如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
					operStack.push(ch);
				}
			}else{
				//如果为空，直接入栈
				operStack.push(ch);
			}
		}else{
			//如果是数，则直接入数栈
			//当处理多为数时，不能发现一个数就直接就入栈，因为可能是多位数】
			//在处理数时，需要向expression的表达式的index后再看一位，如果是数就进行扫描，如果是符号就入栈
			//因此需要定义一个变量 字符串，用于拼接
			keepNum += ch;
			//如果ch已经是expression的最后一位，就直接入栈
			if(index == expression.length() - 1){
				numStack.push(Integer.parseInt(keepNum));
			}else{
				//判断字符串是不是数字，如果是数字就继续扫描，如果是运算符就入栈
				if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
					//如果后以为是运算符，则入栈
					numStack.push(Integer.parseInt(keepNum));
					//这里keepNum要置空
					keepNum="";
				}
			}
		}
		//让index + 1，并判断是否扫描到expression
		index++;
		if(index >= expression.length()){
			break;
		}
	}
	//当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号并运行。
	while(true){
		//如果符号栈为空，则计算到最后的结果，数栈只有一个数字，这个就是结果
		if(operStack.isEmpty())break;
		num1 = numStack.pop();
		num2 = numStack.pop();
		oper = operStack.pop();
		res = numStack.cal(num1, num2, oper);
		numStack.push(res);
	}
	//将数栈最后的结果pop出来
	System.out.printf("表达式%s = %d",expression,numStack.pop());
}

结果：

1	表达式3+2*6-2 = 13

前缀表达式（波兰表达式）

前缀表达式的计算机求值：
从右向左扫描表达式，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程知道表达式最左端，最后运算得出的值即为表达式的结果。
例如：(3+4)X5-6对应的前缀表达式就是- X + 3 4 5 6 ,针对前缀表达式求值步骤如下：
[1]从右至左扫描，将6、5、4压入堆栈。
[2]遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算3+4的值，得7，再将7入栈。
[3]接下来是X运算符，因此弹出7和5，计算出7X5=35，将35入栈。
[4]最后是-运算符，计算出35-6的值，即29.由此得出最终结果。
后缀表达式（逆波兰表达式）
后缀表达式
[1]后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
[2]举例说明：(3+4)X5-6对应的后缀表达式就是3 4 + 5 X 6 -
[3]再比如
a+b 对应的后缀表达式为 a b +
a+(b-c) 对应的后缀表达式为 a b c - +
a+(b-c)d 对应的后缀表达式为 a b c - d * +
a+d(b-c) 对应的后缀表达式为 a d b c - * +
a=1+3 对应的后缀表达式为 a 1 3 + =
后缀表达式的计算机求值
从左向右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程知道表达式最右端，最后运算符得出的值即为表达式的结果。
例如：(3+4)X5-6对应的后缀表达式就是3 4 + 5 X 6 -，针对后缀表达式求值步骤如下：
[1]从左向右扫描，将3和4压入堆栈；
[2]遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
[3]将5入栈；
[4]接下来是X运算符，因此弹出5和7，计算7X5=35，将35入栈;
[5]将6入栈；
[6]最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
逆波兰计算器代码实现
逆波兰计算器，完成任务如下：
[1]输入一个逆波兰表达式(后缀表达式)，使用栈（Stack），计算其结果
[2]支持小括号和多位数整数
思路：
(3+4)X5-6对应的后缀表达式就是3 4 + 5 X 6 -，针对后缀表达式求值步骤如下：
[1]从左向右扫描，将3和4压入堆栈；
[2]遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
[3]将5入栈；
[4]接下来是X运算符，因此弹出5和7，计算7X5=35，将35入栈;
[5]将6入栈；
[6]最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
	public static void main(String[] args) {
		//定义一个逆波兰表达式
		//(3+4)x5-6 => 3 4 + 5 x 6 -
		//为了方便，逆波兰表达式中的数字和符号使用空格隔开
		String suffixExpression = "3 4 + 5 * 6 -";
		//思路
		//1、向将"3 4 + 5 x 6 -" => 放入ArrayList中
		//2、将ArrayList传递给一个方法，遍历ArrayList 配合栈完成计算
		List<String> list = getListString(suffixExpression);
		System.out.println("rpnList="+list);
		int res = calculate(list);
		System.out.println("计算的结果为="+res);
	}
	//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
	public static List<String> getListString(String suffixExpression){
		//将suffixExpression分割
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele : split){
			list.add(ele);
		}
		return list;
	}
	/* 完成对逆波兰表达式的运算
	 * (3+4)X5-6对应的后缀表达式就是3 4 + 5 X 6 -，针对后缀表达式求值步骤如下：
	 * [1]从左向右扫描，将3和4压入堆栈；
	 * [2]遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
	 * [3]将5入栈；
	 * [4]接下来是X运算符，因此弹出5和7，计算7X5=35，将35入栈;
	 * [5]将6入栈；
	 * [6]最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
	 */
	public static int calculate(List<String> ls){
		//创建一个栈,只需要一个栈即可
		Stack<String> stack = new Stack<String>();
		//遍历
		for(String item : ls){
			//这里使用一个正则表达式取出数
			if(item.matches("\\d+")){//匹配的是多位数
				//入栈
				stack.push(item);
			}else{
				//pop出两个数，并运算，再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = 0;
				if(item.equals("+")){
					res = num1 + num2;
				}else if(item.equals("-")){
					res = num1 - num2;
				}else if(item.equals("*")){
					res = num1 * num2;
				}else if(item.equals("/")){
					res = num1 / num2;
				}else{
					throw new RuntimeException("运算符有误");
				}
				//把res入栈
				stack.push(res+"");
			}
		}
		//最后留在stack中的数据就是运算结果
		return Integer.parseInt(stack.pop());
	}
}

结果：

1 2	rpnList=[3, 4, +, 5, *, 6, -] 计算的结果为=29

中缀表达式转换为后缀表达式

从上面的案例可以看出，后缀表达式适合计算机进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

具体步骤如下：
[1]初始化两个栈：运算符栈s1和储存中间结果的栈s2；
[2]从左向右扫描中缀表达式；
[3]遇到操作数时，将其压s2；
[4]遇到运算符时，比较其与s1栈顶运算符的优先级：
（1）如果s1为空，或栈顶运算符为左括号”（“，则直接将此运算符入栈；
（2）否则，若优先级比栈顶运算符的高，也将元算符压入s1；
（3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较。
[5]遇到括号时：
（1）如果是左括号“（”，则直接压入s1；
（2）如果是右括号“）”，则异常弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
[6]重复步骤2-5，直到表达式的最右边；
[7]将s1中剩余的运算符依次弹出并压入s2；
[8]依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

例如：1+((2+3)X4)-5 其转换过程如下表：
在这里插入图片描述

代码实现：
编写一个类Operation 实现可以返回一个运算符对应的优先级数字

//编写一个类Operration 可以返回一个运算符对应的优先级
class Operation{
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;
	//写一个方法，返回一个优先级数字
	public static int getValue(String operation){
		int result = 0;
		switch (operation) {
		case "+":
			result = ADD;
			break;
		case "-":
			result = SUB;
			break;
		case "*":
			result = MUL;
			break;
		case "/":
			result = DIV;
			break;
		default:
		}
		return result;
	}
}

书写可以将一个中缀表达式字符串转换成字符然后返回List的方法

//将中缀表达式转换成对应的List
public static List<String> toInfixExpressionList(String s){
	//定义一个list，存放中缀表达式对应的内容
	List<String> ls = new ArrayList<String>();
	int i = 0;//相当于一个指针，用于遍历中缀表达式字符串
	String str;//做多为数的拼接
	char c;//每对应一个字符，就放入c中
	do{
		//如果c是一个非数字，就需要加入到ls
		if((c=s.charAt(i))<48||(c=s.charAt(i))>57){
			ls.add(""+c);
			i++;//i需要后移
		}else{//如果c是一个数字，需要考虑多为数的问题
			str = "";//先将str置成空
			while(i < s.length() && (c=s.charAt(i))>=48 && (c=s.charAt(i))<=57){
				str +=c;//拼接
				i++;
			}
			ls.add(str);
		}
	}while(i<s.length());
	return ls;
}

书写一个可以将中缀表达式对应的List转换成后缀表达式对应的List的方法

//将中缀表达式转换成对应的后缀表达式
//即ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList[1,2,3,+,4,*,+,5,-]
public static List<String> parseSuffixExpressionList(List<String> ls){
	//定义两个栈
	Stack<String> s1 = new Stack<String>();// 符号栈
	//因为s2这个栈，在转换过程中，没有pop操错，后面还要逆序输出，因此可以直接使用List替代
	List<String> s2 = new ArrayList<String>();//存储中间结果的List s2
	//遍历ls
	for(String item : ls){
		//如果是一个数，加入s2
		if(item.matches("\\d+")){
			s2.add(item);
		}else if(item.equals("(")){
			s1.push(item);
		}else if(item.equals(")")){
			//如果是右括号“）”，则异常弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
			while(!s1.peek().equals("(")){
				s2.add(s1.pop());
			}
			s1.pop();//将这个小括号(弹出s1栈，消除小括号
		}else {
			//当item的优先级小于等于s1栈顶运算符的优先级，将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
			while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
				s2.add(s1.pop());
			}
			//还需要将item压入栈中
			s1.push(item);
		}
	}
	//将s1中剩余的运算符依次弹出并加入s2
	while(s1.size()!=0){
		s2.add(s1.pop());
	}
	return s2; //注意因为是存放到List，因此按顺序输出就是对应的逆波兰表达式
}

测试：

public static void main(String[] args) {
	
	//完成将一个中缀表达式转换成后缀表达式的功能
	//说明
	//1、1+((3+3)*4)-5 转成 1 2 3 + 4 * + 5 -
	//2、因为直接对一个字符串进行操作，不方便，因此先将“1+((3+3)*4)-5”转成中缀表达式对应的List
	//   即“1+((3+3)*4)-5” => ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]
	//3、得到的中缀表达式对应的List转成一个后缀表达式的List
	//	  即ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList[1,2,3,+,4,*,+,5,-]
	String expreession = "1+((2+3)*4)-5";
	List<String> infixExpressionList = toInfixExpressionList(expreession);
	System.out.println("中缀表达式对应的List："+infixExpressionList);
	List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
	System.out.println("后缀表达式对应的List："+parseSuffixExpressionList);
}

结果：

1 2	中缀表达式对应的List：[1, +, (, (, 2, +, 3, ), , 4, ), -, 5] 后缀表达式对应的List：[1, 2, 3, +, 4, , +, 5, -]

数据结构和算法-栈（[逆]波兰表达式）

数据结构和算法-栈（[逆]波兰表达式）

出栈和入栈

栈的应用场景

栈的快速入门

栈实现综合计算器（中缀表达式）

前缀表达式（波兰表达式）

后缀表达式（逆波兰表达式）

逆波兰计算器代码实现

中缀表达式转换为后缀表达式